package midalgorithms.arrandstr;

public class _05LongestPalindrome {
    public static String longestPalindrome(String s) {
        //  最长回文子串
        //  尝试动态规划法
        //  dp[i][j] = (s[i] == s[j]) || (dp[i+1][j-1] && j-i < 3)
        int len = s.length();
        if (len < 2){
            return s;
        }
        boolean[][] dp = new boolean[len][len];
        //  先填充对角线元素
        for (int i = 0;i < len;i++){
            dp[i][i] = true;
        }
        char[] chars = s.toCharArray();
        int begin = 0,maxLen = 1;   //  maxLen = j - i + 1
        for (int i = 0;i < len - 1;i++){
            for (int j = i + 1;j >= 0;j--){
                //  优先填写下方元素
                if (chars[i] != chars[j]){
                    dp[i][j] = false;
                }else {
                    if (j - i < 3){
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                //  注意必须在dp[i][j]成立的时候操作！
                if (dp[i][j] && j-i+1 > maxLen){
                    begin = i;
                    maxLen = j - i + 1;
                }
            }
        }
        return String.valueOf(chars,begin,maxLen);
    }
}
